package cn.cxq.learning.dynamic_programming;

/**
 * 牛客题霸-全部题目
 * 牛妹的礼物
 * 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 128M，其他语言256M 热度指数：10157
 * 本题知识点： 动态规划
 *  算法知识视频讲解
 * 题目描述
 * 众所周知，牛妹有很多很多粉丝，粉丝送了很多很多礼物给牛妹，牛妹的礼物摆满了地板。
 * 地板是N\times MN×M的格子，每个格子有且只有一个礼物，牛妹已知每个礼物的体积。
 * 地板的坐标是左上角(1,1)  右下角（N, M）。
 * 牛妹只想要从屋子左上角走到右下角，每次走一步，每步只能向下走一步或者向右走一步或者向右下走一步
 * 每次走过一个格子，拿起（并且必须拿上）这个格子上的礼物。
 * 牛妹想知道，她能走到最后拿起的所有礼物体积最小和是多少？
 * 示例1
 * 输入
 * 复制
 * [[1,2,3],[2,3,4]]
 * 返回值
 * 复制
 * 7
 * 说明
 * 先走到(1,1)这个点，此时和为1，然后走到(1,2)这个点，拿起(1,2)点的数字，此时和为3，最后走到(2,3)，拿起(2,3)点的数字，此时和为7
 * 备注:
 * 0<N,M<300
 * 0<=每个礼物的体积<100
 */
public class SelectPresent {

    // 动态规划解题
    public int selectPresent (int[][] presentVolumn) {
        // write code here
        if (presentVolumn.length == 0 || presentVolumn[0].length == 0) {
            return 0;
        }

        int[][] dp = new int[presentVolumn.length][presentVolumn[0].length];

        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                dp[i][j] = Integer.MAX_VALUE;
            }
        }

        for (int i = 0; i < presentVolumn.length; i++) {
            for(int j = 0; j < presentVolumn[0].length; j++) {
                if (i != 0 && j != 0) {
                    dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - 1]);
                }
                if (i != 0) {
                    dp[i][j] = Math.min(dp[i][j], dp[i - 1][j]);
                }
                if (j != 0) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][j - 1]);
                }
                if (dp[i][j] == Integer.MAX_VALUE) {
                    dp[i][j] = 0;
                }
                dp[i][j] += presentVolumn[i][j];
            }
        }

        return dp[presentVolumn.length - 1][presentVolumn[0].length - 1];
    }
}
